from collections import deque


class Solution:
    def isValid(self, s: str) -> bool:
        valid_map = {
            "(": ")",
            "[": "]",
            "{": "}",
        }
        st = []
        for tmp in s:
            if tmp in valid_map:
                st.append(valid_map[tmp])
            elif not st or st[-1] != tmp:
                return False
            else:
                st.pop()

        return not bool(st)


print(Solution().isValid("(){}}{"))